class Solution {
public:
    int dp[305][305];
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        for (int i = 1; i < nums.size() - 1; i++) dp[i][i] = nums[i] * nums[i - 1] * nums[i + 1];
        for (int i = 2; i <= nums.size() - 2; i++)
        {
            int l = 1, r = i;
            while (r < nums.size() - 1)
            {
                dp[l][r] = max(dp[l + 1][r] + nums[l] * nums[r + 1] * nums[l - 1], dp[l][r - 1] + nums[r] * nums[l - 1] * nums[r + 1]);
                for (int j = l + 1; j < r; j++) dp[l][r] = max(dp[l][r], dp[l][j - 1] + dp[j + 1][r] + nums[j] * nums[l - 1] * nums[r + 1]);
                r += 1;
                l += 1;
            }
        }
        return dp[1][nums.size() - 2];
    }
};